<?php
// https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/

// 我们用一个大根堆实时维护数组的前 k 小值。首先将前 kk 个数插入大根堆中，随后从第 k+1个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。
class Solution {
    public function getLeastNumbers($arr,  $k) {
        if ($k == 0) {
            return array();
        }

        // 大根堆
        $max_heap = new SplMaxHeap();
        for ($i = 0; $i < $k; ++$i) {
            $max_heap->insert($arr[$i]);
        }

        $vec = array();

        // k开始和堆顶比较，大于堆顶 =》 交换  【堆顶是当前堆最大元素】
        for ($i= $k; $i < count($arr); ++$i) {
            if ($max_heap->top() < $arr[$i]) {
                // 删除堆顶元素
                $max_heap->extract();
                // 插入堆
                $max_heap->insert($arr[$i]);
            }
        }

        for ($i = 0; $i < $k; ++$i) {
            $vec[$i] =  $max_heap->extract();
        }

        return $vec;
    }
}
var_dump((new Solution())->getLeastNumbers([3,2,1], 2));
